⟸ pàgina anterior ⟸
Exercici 9 (Tasca 3).
(theory of languages, Arden's Lemma, hard exercise, regular expressions)

Lema d’Arden i aplicacions

  1. Lema d’Arden. Donats els llenguatges A,B\subseteq \Sigma^* i l’equació X=AX\cup B, \tag{1}

    demostreu que

    1. X=A^*B és solució de (Equació 1), és a dir, A^*B=AA^*B\cup B;
    2. si L és solució de (Equació 1), llavors L\supseteq A^*B;
    3. si \lambda\notin A, llavors A^*B és l’única solució de (Equació 1).

  2. Versió simètrica del Lema d’Arden. Donats els llenguatges A,B\subseteq \Sigma^* i l’equació Y=YA\cup B, \tag{2}

    demostreu que

    1. Y=BA^* és solució de (Equació 2);
    2. si L és solució de (Equació 2), llavors L\supseteq BA^*;
    3. si \lambda\notin A, llavors BA^* és l’única solució de (Equació 2).

  3. Per a cadascun dels llenguatges següents L, doneu un DFA A_L que reconegui L i dues expressions regulars que representin L. Obtingueu les expressions regulars fent servir el lema d’Arden i la versió simètrica del lema d’Arden sobre A_L on

    1. L és el llenguatge dels mots sobre \{a,b\} amb un nombre parell d’as;
    2. L és el llenguatge dels mots sobre \{a,b\} amb o bé un nombre parell d’as o bé un nombre parell de bs;
    3. L és el llenguatge dels mots sobre \{a,b\} que acaben en ababa;
    4. L és el llenguatge dels mots sobre \{a,b\} que no contenen el submot aba;
    5. L és el llenguatge dels mots sobre \{a,b,c\} tals que entre cada dues as hi ha almenys una b;
    6. L és el llenguatge dels mots sobre \{0,1\} amb almenys dos 0s consecutius;
    7. L=\overline{\{w\in \{0,1\}^*\mid \mathtt{value}_2(w)\in 3\mathbb N\}}.
    Consell

    Donat un DFA A, podem associar dues variables a cada estat q: \begin{aligned} X_q&=\text{el llenguatge dels mots que porten de $q$ a un estat acceptador en $A$} \\ Y_q&=\text{el llengutge dels mots que porten de l'estat inicial a $q$ en $A$} \end{aligned} Utilitzant les variables anteriors, podem establir dos sistemes d’equacions i resoldre-les fent ús del lema d’Arden (i de la seva versió simètrica). El sistema que utilitza les variables X_q es pot resoldre amb el lema d’Arden, mentre que el que utilitza Y_q es pot resoldre amb la versió simètrica del lema.